1. Field of the Invention
The present invention relates to a placement method in a semiconductor integrated circuit of a standard cell type or a gate array type, and more specifically to an optimum placement method in a semiconductor integrated circuit for automatically processing an optimum circuit block placement by use of a computer.
2. Description of Related Art
In the prior art, for example, Japanese Patent Application Pre-examination Publication No. JP-A-3-196547, an English abstract of which is available from the Japanese Patent Office and is incorporated by reference in its entirety into this application, proposes an optimum placement method in a semiconductor integrated circuit in order to minimize an area of the integrated circuit and a total wiring length when a placement and layout of circuit blocks are determined by an automatic placement processing using a computer.
Referring to FIG. 1, there is shown a flow chart illustrating one example of the prior art semiconductor integrated circuit placement method proposed by JP-A-3-196547. First, an initial placement is determined (Step S51), and the number of continuous operations of replacing and moving the circuit blocks is determined or set (Step S52). Next, a current placement stats is evaluated (Step S53), and the number of continuous replacing and moving operations of the circuit blocks is compared with a set value (Step S54). If the number of continuous replacing and moving operations is less than the set value, the processing goes into a Step S55 and succeeding steps, where a selection, replacement and movement of the blocks are conducted so that a new placement state is generated, and then, the new placement state is evaluated (Steps S55, S56 and S57). Furthermore, whether or not the new placement state is improved in comparison with the old placement state is discriminated, and if the new placement state is improved, the new placement state is registered, and the number of continuous replacing and moving operations of the circuit blocks made until that time is reset (Steps S58, S60 and S61). To the contrary, if the new placement state is not improved, the number of continuous replacing and moving operations of the circuit blocks is incremented by "1" (Step S59), and the operation of replacing and moving the circuit blocks is repeated.
This prior art semiconductor integrated circuit placement method will be specifically described with reference to FIGS. 2A, 2B, 2C and 2D.
FIG. 2A shows a given initial placement composed of seven circuit blocks 61, 62, 63, 64, 65, 66 and 67, which are interconnected through wiring conductors 7 as shown. Here, assume that the number of continuous replacing and moving operations of the circuit blocks is set to "2". In addition, assuming that a wiring length interconnecting between a pair of adjacent circuit blocks is "1", a total wiring length in the given initial placement becomes "15".
For the purpose of shortening the total wiring length, two circuit blocks 62 and 63 are replaced and moved as shown in FIG. 2B. In this case, however, the total wiring length becomes "17". At this time, since the number of continuous replacing and moving operations has not yet exceeded the set value of "2", two circuit blocks 64 and 65 are further replaced and moved as shown in FIG. 2C. In this case, however, the total wiring length becomes "18". Namely, since the total wiring length in the old or initial placement is "15", the placement state becomes deteriorated. At this time, since the number of continuous replacing and moving operations has exceeded the set value of "2", it is finally judged that the initial placement is the best placement.
As mentioned above, in the prior art method it is judged that the placement shown in FIG. 2A is the best placement. Actually, however, a placement shown in FIG. 2D is possible, and this is the best placement, since the total wiring length is "10".
As seen from the above, in the prior art method, the final placement state greatly depends upon the initial placement state. In addition, if the number of continuous replacing and moving operations is limited to a small value, an improvement processing ends before it reaches the best placement state, and the final placement state is apt to become a local minimum solution which minimizes the wiring length only locally. On the other hand, if the replacing and moving operations of the circuit blocks are continuously repeated in order to obtain the best placement, the number of continuous replacing and moving operations becomes large, and a processing time correspondingly becomes long. In particular, the larger the number of circuit blocks is, the larger the number of continuous replacing and moving operations becomes.
The inventor of the present application examined the cause of the above mentioned problems. A first problem is that the final placement state greatly depends upon the initial placement state. The cause for this first problem is considered that the circuit block replacement and movement is started from a given initial placement. A second problem is that the final placement state depends upon the number of continuous replacing and moving operations of the circuit blocks. The cause for this second problem is considered that if the number of continuous replacing and moving operations is set to a small value, an improvement processing ends before it reaches the best placement state, and the final placement state is apt to become a local minimum solution which minimizes the wiring length only locally, and on the other hand, if the number of continuous replacing and moving operations is set to a large value, the processing time becomes long. A third problem is that the larger the number of circuit blocks is, the larger the number of continuous replacing and moving operations becomes. The cause for this third problem is considered that, in order to obtain the best placement, if the circuit blocks are not replaced throughout, the final placement state is apt to become a local minimum solution which minimizes the wiring length only locally, and therefore, the number of continuous replacing and moving operations executed is apt to be made large.